#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHAR_CODE 128
#define ROOT 1
#define FATHER(i) ((i) / 2)
#define LEFT(i)   ((i) * 2)
#define RIGHT(i)  ((i) * 2 + 1)
#define swap(a, b){\
    __typeof(a)__c = (a);\
    (a) = (b);(b) = __c;\
    }


char *char_code[MAX_CHAR_CODE] = {0};

typedef struct Node {
  char ch;
  int freq;
  Node *lchild, *rchild;
} Node;

typedef struct Heap{
    Node **__data, **data;
    int n, size;
} Heap;

Heap *getNewHeap(int size){
    Heap *h = (Heap *)malloc(sizeof(Heap));
    h->__data = (Node **)malloc(sizeof(Node *) * size);
    h->data = h->__data - 1;
    h->n = 0;
    h->size = size;
    return h;
}

void clearHeap(Heap *h){
    if(h == NULL) return;
    free(h->__data);
    free(h);
    return;
}

int fullHeap(Heap *h){
    return h->n == h->size;
}

void up_update(Heap *h, int i){
    while(i > ROOT && h->data[i]->freq < h->data[FATHER(i)]->freq){
        swap(h->data[i], h->data[FATHER(i)]);
        i = FATHER(i);
    }
    return;
}

void down_update(Heap *h, int i){
    while(LEFT(i) <= h->n){
        int idx = i, l = LEFT(i), r = RIGHT(i);
        if(h->data[l]->freq < h->data[idx]->freq) idx = l;
        if(r <= h->n && h->data[r]->freq < h->data[idx]->freq) idx = r;
        if(idx == i) break;
        swap(h->data[i], h->data[idx]);
        i = idx;
    }
    return;
}

int pushHeap(Heap *h, Node *n){
    if(fullHeap(h)) return 0;
    h->n += 1;
    h->data[h->n] = n;
    up_update(h, h->n);
    return 1;
}

int emptyHeap(Heap *h){
    return h->n == 0;
}

Node *top(Heap *h){
    if(emptyHeap(h)) return NULL;
    return h->data[1];
}

int popHeap(Heap *h){
    if(emptyHeap(h)) return 0;
    h->data[1] = h->data[h->n];
    h->n -= 1;
    down_update(h, 1);
    return 1;
}

Node *getNewNode(int freq, char ch) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->ch = ch;
  p->freq = freq;
  p->lchild = p->rchild = NULL;
  return p;
}

void clear(Node *root) {
  if (root == NULL)
    return;
  clear(root->lchild);
  clear(root->rchild);
  free(root);
  return;
}

void swap_node(Node **node_arr, int i, int j){
    Node *temp = node_arr[i];
    node_arr[i] = node_arr[j];
    node_arr[j] = temp;
    return;
}

int find_min_node(Node **node_arr, int n){
    int ind = 0;
    for(int j = 1; j <= n; j++){
        if(node_arr[ind]->freq > node_arr[j]->freq) ind = j;
    }
    return ind;
}

Node *buildHaffmanTree(Node **node_arr, int n){
    Heap *h = getNewHeap(n);
    for(int i = 0; i < n; i++) pushHeap(h, node_arr[i]);
    for(int i = 1; i < n; i++){
        Node *node1 = top(h);
        popHeap(h);
        Node *node2 = top(h);
        popHeap(h);
        Node *node3 = getNewNode(node1->freq + node2->freq, 0);
        node3->lchild = node1;
        node3->rchild = node2;
        pushHeap(h, node3);
    }
    Node *ret = top(h);
    clearHeap(h);
    return ret;
}

void extractHaffmanCode(Node *root, char buff[], int k){
    buff[k] = 0;
    if(root->lchild == NULL && root->rchild == NULL){
        // printf("%c : %s\n", root->ch, buff);
        char_code[root->ch] = strdup(buff); 
        return;
    }
    buff[k] = '1';
    extractHaffmanCode(root->lchild, buff, k + 1);
    buff[k] = '0';
    extractHaffmanCode(root->rchild, buff, k + 1);
    return;
}

int main(){
    char s[10];
    int n, freq;
    scanf("%d", &n);
    Node **node_arr = (Node **)malloc(sizeof(Node *) * n);
    for (int i = 0; i < n; i++) {
        scanf("%s%d",s, &freq);
        node_arr[i] = getNewNode(freq, s[0]);
    }
    Node *root = buildHaffmanTree(node_arr, n);
    char buff[1000];
    extractHaffmanCode(root, buff, 0);
    for(int i = 0; i < MAX_CHAR_CODE; i++){
        if(char_code[i] == NULL) continue;
        printf("%c : %s\n", i, char_code[i]);
    }
    clear(root);
    
    return 0;
}